package com.dong.binaryTree;

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.util.ArrayList;
import java.util.List;
/*
给你二叉树的根节点 root ，返回它节点值的前序遍历
输入：root = [1,null,2,3]
输出：[1,2,3]
递归实现三种遍历
 */
class TreeNode2 {
    int val;//存放值
    TreeNode2 left;//指向左节点
    TreeNode2 right;//指向右节点
    TreeNode2(){};
    TreeNode2(int val){
        this.val = val;
    }

    public TreeNode2(int val, TreeNode2 left, TreeNode2 right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class PreorderTraversal {
    public List<Integer> preorderTraversal(TreeNode2 root) {
        ArrayList<Integer> result = new ArrayList<>();
        preorder(root,result);
        return result;

    }

    //前序遍历
    public void preorder(TreeNode2 root, List<Integer> result){
        if (root == null){
            return;
        }
        result.add(root.val);
        //当一个方法执行完毕或者遇到return，就会返回，谁调用就结果返回给谁，
        // 同时当该方法方法执行完毕或返回时，该方法也就执行完毕
        preorder(root.left,result);
        preorder(root.right,result);
    }

    //中序遍历
    public void inorder(TreeNode2 root, List<Integer> list) {
         if (root==null){
             return;
         }
         inorder(root.left,list);
         list.add(root.val);
         inorder(root.right,list);
    }

    //后序遍历
    public void postorder(TreeNode2 root, List<Integer> list){
        if (root==null){
            return;
        }
        inorder(root.left,list);
        inorder(root.right,list);
        list.add(root.val);
    }
}
